import java.util.ArrayDeque;
import java.util.Deque;

public class MaxSlidingWindow {
    // 滑动窗口最大值
    // https://leetcode.cn/problems/sliding-window-maximum/?envType=study-plan-v2&envId=top-100-liked
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 单调栈，从栈顶到栈底的元素是从小到大的
        // 如果nums[i]，那么就说明栈顶的元素一定不会是窗口中的最大值，所以可以将栈顶的元素弹出，直到栈顶
        // 的元素大于nums[i]，然后将nums[i]压到栈顶，这样就保证了单调栈的有序性
        if (k > nums.length) {
            return new int[]{};
        }
        int[] ret = new int[nums.length-k+1];
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            if (deque.isEmpty()) {
                deque.offer(i);
            }
            while (!deque.isEmpty() && deque.peekLast() <= i-k) {
                deque.pollLast();
            }
            while (!deque.isEmpty() && nums[i] > nums[deque.peekFirst()]) {
                deque.pollFirst();
            }
            deque.offerFirst(i);
            if (i >= k-1) {
                ret[i-k+1] = nums[deque.peekLast()];
            }
        }
        return ret;
    }
}
